package main

// 最小路径和
// 动态规划问题:
// 动态规划解题思路
// 状态定义：设 dp[i][j] 表示从顶部到达第 i 行第 j 列的最小路径和。
// 状态转移方程：对于第 i 行第 j 列的元素，其路径只能来自上一行的两个相邻节点：
// 若 j = 0（第一列）：只能从上层第 j 列过来，即 dp[i][j] = dp[i-1][j] + triangle[i][j]
// 若 j = i（最后一列）：只能从上层第 j-1 列过来，即 dp[i][j] = dp[i-1][j-1] + triangle[i][j]
// 其他情况：取上层两个相邻节点的最小值，即 dp[i][j] = min(dp[i-1][j-1], dp[i-1][j]) + triangle[i][j]
// 空间优化：观察可知，第 i 行的计算只依赖第 i-1 行，因此可使用一维数组优化空间，将空间复杂度从 O(n²) 降至 O(n)（n 为三角形行数）。
// 自底向上简化：从最后一行向上计算（避免处理顶部边界），最终结果直接存于顶部（dp[0]）。
func minimumTotal(triangle [][]int) int {
	if len(triangle) == 0 {
		return 0
	}
	n := len(triangle)
	dp := make([]int, n)
	for j := 0; j < n; j++ {
		dp[j] = triangle[n-1][j]
	}
	for i := n - 2; i >= 0; i-- {
		for j := 0; j <= i; j++ {
			// 当前dp[j] = 下一行j和j+1的最小值 + 当前元素值
			dp[j] = min(dp[j], dp[j+1]) + triangle[i][j]

		}
	}
	return dp[0]
}
